package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 216. 组合总和 III https://leetcode.cn/problems/combination-sum-iii/
 * 题目简述：找出所有相加之和为n的k个数的组合，组合中：只使用数字1到9，每个数字最多使用一次
 */
public class CombinationSum3 {

    /**
     * 思路：回溯算法。将回溯过程抽象为一棵树形结构
     * 回溯递归函数参数：(结果集result，所需路径长度k，已选择路径，已选择路径总和，下一步路径选择列表）
     * 回溯递归函数体：1.若路径长度已等于k：若总和满足要求则将当前路径添加到结果集。return
     *              2.遍历当前选择列表：将选择加入路径，然后递归下一步的选择列表，完毕后撤销上一步选择，继续遍历同层中的其它选择
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, k, path, 0, 1, n);
        return result;
    }

    public void backTracking(List<List<Integer>> result, int k, Deque<Integer> path, int sum, int begin, int n) {
        if(path.size() == k) {
            if(sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        //遍历当前选择列表[begin，9]。剪枝1：顺序性剪枝，剪去[0,begin)；剪枝2：i到9的长度不能小于还需要的路径长度k - path.size()
        for(int i=begin;i <= 9 - (k - path.size() -1);i++) {
            path.add(i);sum += i;
            if(sum > n) {
                //若总和已大于n，则同层中后续的元素更大 无需遍历，直接return
                path.removeLast();
                return;
            }
            backTracking(result, k, path, sum, i+1, n);
            path.removeLast();sum -= i;
        }
    }
}
